//121. 买卖股票的最佳时机

//给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
//你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
//返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

//class Solution {
//public:
//    int maxProfit(vector<int>& prices) {
//        int ans = 0;
//        int min_price = prices[0];
//        for (int p : prices) {
//            ans = max(ans, p - min_price);
//            min_price = min(min_price, p);
//        }
//        return ans;
//    }
//};

//122. 买卖股票的最佳时机 II

//给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
//在每一天，你可以决定是否购买和 / 或出售股票。你在任何时候 最多 只能持有 一股 股票。然而，你可以在 同一天 多次买卖该股票，但要确保你持有的股票不超过一股。
//返回 你能获得的 最大 利润 。

//class Solution {
//public:
//    int maxProfit(vector<int>& prices) {
//        int f0 = 0, f1 = INT_MIN;
//        for (int p : prices) {
//            int new_f0 = max(f0, f1 + p);
//            f1 = max(f1, f0 - p);
//            f0 = new_f0;
//        }
//        return f0;
//    }
//};

//123. 买卖股票的最佳时机 III

//给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
//设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
//注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

//class Solution {
//public:
//    int maxProfit(vector<int>& prices) {
//        const int k = 2;
//        vector<array<int, 2>> f(k + 2, { -0x3f3f3f3f, -0x3f3f3f3f });
//        for (int j = 1; j <= k + 1; j++) {
//            f[j][0] = 0;
//        }
//        for (int p : prices) {
//            for (int j = k + 1; j > 0; j--) {
//                f[j][0] = max(f[j][0], f[j][1] + p);
//                f[j][1] = max(f[j][1], f[j - 1][0] - p);
//            }
//        }
//        return f[k + 1][0];
//    }
//};

//188. 买卖股票的最佳时机 IV

//给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。
//设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
//注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

//class Solution {
//public:
//    int maxProfit(int k, vector<int>& prices) {
//        int n = prices.size();
//        vector f(n + 1, vector<array<int, 2>>(k + 2, { -0x3f3f3f3f, -0x3f3f3f3f }));
//        for (int j = 1; j <= k + 1; j++) {
//            f[0][j][0] = 0;
//        }
//        for (int i = 0; i < n; i++) {
//            for (int j = 1; j <= k + 1; j++) {
//                f[i + 1][j][0] = max(f[i][j][0], f[i][j][1] + prices[i]);
//                f[i + 1][j][1] = max(f[i][j][1], f[i][j - 1][0] - prices[i]);
//            }
//        }
//        return f[n][k + 1][0];
//    }
//};

//3573. 买卖股票的最佳时机 V

//给你一个整数数组 prices，其中 prices[i] 是第 i 天股票的价格（美元），以及一个整数 k。
//你最多可以进行 k 笔交易，每笔交易可以是以下任一类型：
//普通交易：在第 i 天买入，然后在之后的第 j 天卖出，其中 i < j。你的利润是 prices[j] - prices[i]。
//做空交易：在第 i 天卖出，然后在之后的第 j 天买回，其中 i < j。你的利润是 prices[i] - prices[j]。
//注意：你必须在开始下一笔交易之前完成当前交易。此外，你不能在已经进行买入或卖出操作的同一天再次进行买入或卖出操作。
//通过进行 最多 k 笔交易，返回你可以获得的最大总利润。

//class Solution {
//public:
//    long long maximumProfit(vector<int>& prices, int k) {
//        int n = prices.size();
//        vector f(n + 1, vector<array<long long, 3>>(k + 2, { LLONG_MIN / 2, LLONG_MIN / 2, LLONG_MIN / 2 }));
//        for (int j = 1; j <= k + 1; j++) {
//            f[0][j][0] = 0;
//        }
//        for (int i = 0; i < n; i++) {
//            int p = prices[i];
//            for (int j = 1; j <= k + 1; j++) {
//                f[i + 1][j][0] = max({ f[i][j][0], f[i][j][1] + p, f[i][j][2] - p });
//                f[i + 1][j][1] = max(f[i][j][1], f[i][j - 1][0] - p);
//                f[i + 1][j][2] = max(f[i][j][2], f[i][j - 1][0] + p);
//            }
//        }
//        return f[n][k + 1][0];
//    }
//};

//309. 买卖股票的最佳时机含冷冻期

//给定一个整数数组prices，其中第  prices[i] 表示第 i 天的股票价格 。​
//设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票） :
//卖出股票后，你无法在第二天买入股票(即冷冻期为 1 天)。
//注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

//class Solution {
//public:
//    int maxProfit(vector<int>& prices) {
//        int n = prices.size();
//        vector<array<int, 2>> f(n + 2);
//        f[1][1] = INT_MIN;
//        for (int i = 0; i < n; i++) {
//            f[i + 2][0] = max(f[i + 1][0], f[i + 1][1] + prices[i]);
//            f[i + 2][1] = max(f[i + 1][1], f[i][0] - prices[i]);
//        }
//        return f[n + 1][0];
//    }
//};

//714. 买卖股票的最佳时机含手续费

//给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。
//你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
//返回获得利润的最大值。
//注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

//class Solution {
//public:
//    int maxProfit(vector<int>& prices, int fee) {
//        int n = prices.size();
//        vector<array<int, 2>> f(n + 1);
//        f[0][1] = INT_MIN / 2;
//        for (int i = 0; i < n; i++) {
//            f[i + 1][0] = max(f[i][0], f[i][1] + prices[i] - fee);
//            f[i + 1][1] = max(f[i][1], f[i][0] - prices[i]);
//        }
//        return f[n][0];
//    }
//};

//3259. 超级饮料的最大强化能量

//来自未来的体育科学家给你两个整数数组 energyDrinkA 和 energyDrinkB，数组长度都等于 n。这两个数组分别代表 A、B 两种不同能量饮料每小时所能提供的强化能量。
//你需要每小时饮用一种能量饮料来 最大化 你的总强化能量。然而，如果从一种能量饮料切换到另一种，你需要等待一小时来梳理身体的能量体系（在那个小时里你将不会获得任何强化能量）。
//返回在接下来的 n 小时内你能获得的 最大 总强化能量。
//注意 你可以选择从饮用任意一种能量饮料开始。

//class Solution {
//public:
//    long long maxEnergyBoost(vector<int>& a, vector<int>& b) {
//        int n = a.size();
//        vector<array<long long, 2>> f(n + 2);
//        for (int i = 0; i < n; i++) {
//            f[i + 2][0] = max(f[i + 1][0], f[i][1]) + a[i];
//            f[i + 2][1] = max(f[i + 1][1], f[i][0]) + b[i];
//        }
//        return max(f[n + 1][0], f[n + 1][1]);
//    }
//};

//2222. 选择建筑的方案数

//给你一个下标从 0 开始的二进制字符串 s ，它表示一条街沿途的建筑类型，其中：
//s[i] = '0' 表示第 i 栋建筑是一栋办公楼，
//s[i] = '1' 表示第 i 栋建筑是一间餐厅。
//作为市政厅的官员，你需要随机 选择 3 栋建筑。然而，为了确保多样性，选出来的 3 栋建筑 相邻 的两栋不能是同一类型。
//比方说，给你 s = "001101" ，我们不能选择第 1 ，3 和 5 栋建筑，因为得到的子序列是 "011" ，有相邻两栋建筑是同一类型，所以 不合 题意。
//请你返回可以选择 3 栋建筑的 有效方案数 。

//class Solution {
//public:
//    long long numberOfWays(string s) {
//        int r1 = s.size(), r0 = 0;
//        for (char& c : s) {
//            if (c == '0') {
//                r0++;
//            }
//        }
//        r1 -= r0;
//        long long l0 = 0, l1 = 0;
//        long long ans = 0;
//        for (char& c : s) {
//            if (c == '0') {
//                r0--;
//                l0++;
//                ans += l1 * r1;
//            }
//            else {
//                r1--;
//                l1++;
//                ans += l0 * r0;
//            }
//        }
//        return ans;
//    }
//};

//2708. 一个小组的最大实力值

//给你一个下标从 0 开始的整数数组 nums ，它表示一个班级中所有学生在一次考试中的成绩。
//老师想选出一部分同学组成一个 非空 小组，且这个小组的 实力值 最大，如果这个小组里的学生下标为 i0, i1, i2, ..., ik ，
//那么这个小组的实力值定义为 nums[i0] * nums[i1] * nums[i2] * ... * nums[ik​] 。
//请你返回老师创建的小组能得到的最大实力值为多少

//class Solution {
//public:
//    long long maxStrength(vector<int>& nums) {
//        long long mn = nums[0], mx = mn;
//        for (int i = 1; i < nums.size(); i++) {
//            long long x = nums[i];
//            long long tmp = mn;
//            mn = min({ mn, x, mn * x, mx * x });
//            mx = max({ mx, x, tmp * x, mx * x });
//        }
//        return mx;
//    }
//};

//1567. 乘积为正数的最长子数组长度

//给你一个整数数组 nums ，请你求出乘积为正数的最长子数组的长度。
//一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。
//请你返回乘积为正数的最长子数组长度。

//class Solution {
//public:
//    int getMaxLen(vector<int>& nums) {
//        int length = nums.size();
//        vector<int> positive(length), negative(length);
//        if (nums[0] > 0) {
//            positive[0] = 1;
//        }
//        else if (nums[0] < 0) {
//            negative[0] = 1;
//        }
//        int maxLength = positive[0];
//        for (int i = 1; i < length; ++i) {
//            if (nums[i] > 0) {
//                positive[i] = positive[i - 1] + 1;
//                negative[i] = (negative[i - 1] > 0 ? negative[i - 1] + 1 : 0);
//            }
//            else if (nums[i] < 0) {
//                positive[i] = (negative[i - 1] > 0 ? negative[i - 1] + 1 : 0);
//                negative[i] = positive[i - 1] + 1;
//            }
//            else {
//                positive[i] = 0;
//                negative[i] = 0;
//            }
//            maxLength = max(maxLength, positive[i]);
//        }
//        return maxLength;
//    }
//};

//2786. 访问数组中的位置使分数最大

//给你一个下标从 0 开始的整数数组 nums 和一个正整数 x 。
//你 一开始 在数组的位置 0 处，你可以按照下述规则访问数组中的其他位置：
//如果你当前在位置 i ，那么你可以移动到满足 i < j 的 任意 位置 j 。
//对于你访问的位置 i ，你可以获得分数 nums[i] 。
//如果你从位置 i 移动到位置 j 且 nums[i] 和 nums[j] 的 奇偶性 不同，那么你将失去分数 x 。
//请你返回你能得到的 最大 得分之和。
//注意 ，你一开始的分数为 nums[0] 。

//class Solution {
//public:
//    long long maxScore(vector<int>& nums, int x) {
//        int n = nums.size();
//        vector<array<long long, 2>> f(n + 1);
//        for (int i = n - 1; i >= 0; i--) {
//            int v = nums[i];
//            int r = v % 2;
//            f[i][r ^ 1] = f[i + 1][r ^ 1]; // v%2 != j 的情况
//            f[i][r] = max(f[i + 1][r], f[i + 1][r ^ 1] - x) + v;
//        }
//        return f[0][nums[0] % 2];
//    }
//};

//1911. 最大交替子序列和

//一个下标从 0 开始的数组的 交替和 定义为 偶数 下标处元素之 和 减去 奇数 下标处元素之 和 。
//比方说，数组[4, 2, 5, 3] 的交替和为(4 + 5) - (2 + 3) = 4 。
//给你一个数组 nums ，请你返回 nums 中任意子序列的 最大交替和 （子序列的下标 重新 从 0 开始编号）。
//一个数组的 子序列 是从原数组中删除一些元素后（也可能一个也不删除）剩余元素不改变顺序组成的数组。
//比方说，[2, 7, 4] 是[4, 2, 3, 7, 2, 1, 4] 的一个子序列（加粗元素），但是[2, 4, 2] 不是。

//class Solution {
//public:
//    long long maxAlternatingSum(vector<int>& nums) {
//        int n = nums.size();
//        long long f[n + 1][2];
//        f[0][0] = 0;
//        f[0][1] = INT_MIN;
//        for (int i = 0; i < n; i++) {
//            f[i + 1][0] = max(f[i][0], f[i][1] - nums[i]);
//            f[i + 1][1] = max(f[i][1], f[i][0] + nums[i]);
//        }
//        return max(f[n][0], f[n][1]);
//    }
//};

//376. 摆动序列

//如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
//例如，[1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值(6, -3, 5, -7, 3) 是正负交替出现的。
//相反，[1, 4, 7, 2, 5] 和[1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
//子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。
//给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。

//class Solution {
//public:
//    int wiggleMaxLength(vector<int>& nums) {
//        int n = nums.size();
//        if (n < 2) {
//            return n;
//        }
//        vector<int> up(n), down(n);
//        up[0] = down[0] = 1;
//        for (int i = 1; i < n; i++) {
//            if (nums[i] > nums[i - 1]) {
//                up[i] = max(up[i - 1], down[i - 1] + 1);
//                down[i] = down[i - 1];
//            }
//            else if (nums[i] < nums[i - 1]) {
//                up[i] = up[i - 1];
//                down[i] = max(up[i - 1] + 1, down[i - 1]);
//            }
//            else {
//                up[i] = up[i - 1];
//                down[i] = down[i - 1];
//            }
//        }
//        return max(up[n - 1], down[n - 1]);
//    }
//};

//3628. 插入一个字母的最大子序列数

//给你一个由大写英文字母组成的字符串 s。
//你可以在字符串的 任意 位置（包括字符串的开头或结尾）最多插入一个 大写英文字母。
//返回在 最多插入一个字母 后，字符串中可以形成的 "LCT" 子序列的 最大 数量。
//子序列 是从另一个字符串中删除某些字符（可以不删除）且不改变剩余字符顺序后得到的一个 非空 字符串。

//class Solution {
//public:
//    long long numOfSubsequences(string s) {
//        int t = ranges::count(s, 'T');
//        long long l = 0, lc = 0, lct = 0, c = 0, ct = 0, lt = 0;
//        for (char b : s) {
//            if (b == 'L') {
//                l++;
//            }
//            else if (b == 'C') {
//                lc += l;
//                c++;
//            }
//            else if (b == 'T') {
//                lct += lc;
//                ct += c;
//                t--;
//            }
//            lt = max(lt, l * t);
//        }
//        return lct + max({ ct, lc, lt });
//    }
//};

//2771. 构造最长非递减子数组

//给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，长度均为 n 。
//让我们定义另一个下标从 0 开始、长度为 n 的整数数组，nums3 。对于范围[0, n - 1] 的每个下标 i ，你可以将 nums1[i] 或 nums2[i] 的值赋给 nums3[i] 。
//你的任务是使用最优策略为 nums3 赋值，以最大化 nums3 中 最长非递减子数组 的长度。
//以整数形式表示并返回 nums3 中 最长非递减 子数组的长度。
//注意：子数组 是数组中的一个连续非空元素序列。

//class Solution {
//public:
//    int maxNonDecreasingLength(vector<int>& nums1, vector<int>& nums2) {
//        int n = nums1.size(), f[n][2];
//        f[0][0] = f[0][1] = 1;
//        vector<vector<int>> nums(2, vector<int>(n));
//        nums[0] = { nums1.begin(),nums1.end() };
//        nums[1] = { nums2.begin(),nums2.end() };
//        int mx = 1;
//        for (int i = 1; i < n; i++) {
//            for (int j = 0; j < 2; j++) {
//                f[i][j] = 1;
//                if (nums1[i - 1] <= nums[j][i]) f[i][j] = f[i - 1][0] + 1;
//                if (nums2[i - 1] <= nums[j][i]) f[i][j] = max(f[i][j], f[i - 1][1] + 1);
//                mx = max(mx, f[i][j]);
//            }
//
//        }
//        return mx;
//    }
//};

//1186. 删除一次得到子数组最大和

//给你一个整数数组，返回它的某个 非空 子数组（连续元素）在执行一次可选的删除操作后，所能得到的最大元素总和。
//换句话说，你可以从原数组中选出一个子数组，并可以决定要不要从中删除一个元素（只能删一次哦），（删除后）子数组中至少应当有一个元素，然后该子数组（剩下）的元素总和是所有子数组之中最大的。
//注意，删除一个元素后，子数组 不能为空。

//class Solution {
//public:
//    int maximumSum(vector<int>& arr) {
//        int n = arr.size();
//        vector<array<int, 2>> f(n + 1, { INT_MIN / 2, INT_MIN / 2 });
//        int ans = INT_MIN;
//        for (int i = 0; i < n; i++) {
//            f[i + 1][0] = max(f[i][0], 0) + arr[i];
//            f[i + 1][1] = max(f[i][1] + arr[i], f[i][0]);
//            ans = max(ans, max(f[i + 1][0], f[i + 1][1]));
//        }
//        return ans;
//    }
//};

//1594. 矩阵的最大非负积

//给你一个大小为 m x n 的矩阵 grid 。最初，你位于左上角(0, 0) ，每一步，你可以在矩阵中 向右 或 向下 移动。
//在从左上角(0, 0) 开始到右下角(m - 1, n - 1) 结束的所有路径中，找出具有 最大非负积 的路径。路径的积是沿路径访问的单元格中所有整数的乘积。
//返回 最大非负积 对 109 + 7 取余 的结果。如果最大积为 负数 ，则返回 - 1 。
//注意，取余是在得到最大积之后执行的。

//class Solution {
//public:
//    int maxProductPath(vector<vector<int>>& grid) {
//        const int mod = 1000000007;
//        int m = grid.size(), n = grid[0].size();
//        vector<vector<long long>> maxgt(m, vector<long long>(n));
//        vector<vector<long long>> minlt(m, vector<long long>(n));
//
//        maxgt[0][0] = minlt[0][0] = grid[0][0];
//        for (int i = 1; i < n; i++) {
//            maxgt[0][i] = minlt[0][i] = maxgt[0][i - 1] * grid[0][i];
//        }
//        for (int i = 1; i < m; i++) {
//            maxgt[i][0] = minlt[i][0] = maxgt[i - 1][0] * grid[i][0];
//        }
//
//        for (int i = 1; i < m; i++) {
//            for (int j = 1; j < n; j++) {
//                if (grid[i][j] >= 0) {
//                    maxgt[i][j] = max(maxgt[i][j - 1], maxgt[i - 1][j]) * grid[i][j];
//                    minlt[i][j] = min(minlt[i][j - 1], minlt[i - 1][j]) * grid[i][j];
//                }
//                else {
//                    maxgt[i][j] = min(minlt[i][j - 1], minlt[i - 1][j]) * grid[i][j];
//                    minlt[i][j] = max(maxgt[i][j - 1], maxgt[i - 1][j]) * grid[i][j];
//                }
//            }
//        }
//        if (maxgt[m - 1][n - 1] < 0) {
//            return -1;
//        }
//        else {
//            return maxgt[m - 1][n - 1] % mod;
//        }
//    }
//};

//3196. 最大化子数组的总成本

//给你一个长度为 n 的整数数组 nums。
//子数组 nums[l..r]（其中 0 <= l <= r < n）的 成本 定义为：
//cost(l, r) = nums[l] - nums[l + 1] + ... + nums[r] * (−1)r − l
//你的任务是将 nums 分割成若干子数组，使得所有子数组的成本之和 最大化，并确保每个元素 正好 属于一个子数组。
//具体来说，如果 nums 被分割成 k 个子数组，且分割点为索引 i1, i2, ..., ik − 1（其中 0 <= i1 < i2 < ... < ik - 1 < n - 1），则总成本为：
//cost(0, i1) + cost(i1 + 1, i2) + ... + cost(ik − 1 + 1, n − 1)
//返回在最优分割方式下的子数组成本之和的最大值。
//注意：如果 nums 没有被分割，即 k = 1，则总成本即为 cost(0, n - 1)。

//class Solution {
//public:
//    long long maximumTotalCost(vector<int>& a) {
//        int n = a.size();
//        vector<long long> f(n + 1);
//        f[1] = a[0];
//        for (int i = 1; i < n; i++) {
//            f[i + 1] = max(f[i] + a[i], f[i - 1] + a[i - 1] - a[i]);
//        }
//        return f[n];
//    }
//};

//935. 骑士拨号器

//象棋骑士有一个独特的移动方式，它可以垂直移动两个方格，水平移动一个方格，或者水平移动两个方格，垂直移动一个方格(两者都形成一个 L 的形状)。
//象棋骑士可能的移动方式如下图所示 :
//我们有一个象棋骑士和一个电话垫，如下所示，骑士只能站在一个数字单元格上(即蓝色单元格)。
//给定一个整数 n，返回我们可以拨多少个长度为 n 的不同电话号码。
//你可以将骑士放置在任何数字单元格上，然后你应该执行 n - 1 次移动来获得长度为 n 的号码。所有的跳跃应该是有效的骑士跳跃。
//因为答案可能很大，所以输出答案模 109 + 7.

//const int MOD = 1'000'000'007;
//const int MX = 5000;
//long long f[MX][4];
//
//int init = []() {
//    f[0][0] = f[0][1] = f[0][2] = f[0][3] = 1;
//    for (int i = 1; i < MX; i++) {
//        f[i][0] = (f[i - 1][1] + f[i - 1][2]) % MOD;
//        f[i][1] = f[i - 1][0] * 2 % MOD;
//        f[i][2] = (f[i - 1][0] * 2 + f[i - 1][3]) % MOD;
//        f[i][3] = f[i - 1][2] * 2 % MOD;
//    }
//    return 0;
//    }();
//
//class Solution {
//public:
//    int knightDialer(int n) {
//        if (n == 1) {
//            return 10;
//        }
//        return (f[n - 1][0] * 4 + f[n - 1][1] * 2 + f[n - 1][2] * 2 + f[n - 1][3]) % MOD;
//    }
//};

//1537. 最大得分

//你有两个 有序 且数组内元素互不相同的数组 nums1 和 nums2 。
//一条 合法路径 定义如下：
//选择数组 nums1 或者 nums2 开始遍历（从下标 0 处开始）。
//从左到右遍历当前数组。
//如果你遇到了 nums1 和 nums2 中都存在的值，那么你可以切换路径到另一个数组对应数字处继续遍历（但在合法路径中重复数字只会被统计一次）。
//得分 定义为合法路径中不同数字的和。
//请你返回 所有可能 合法路径 中的最大得分。由于答案可能很大，请你将它对 10 ^ 9 + 7 取余后返回。

//class Solution {
//private:
//    static constexpr int mod = 1000000007;
//
//public:
//    int maxSum(vector<int>& nums1, vector<int>& nums2) {
//        int m = nums1.size();
//        int n = nums2.size();
//        long long best1 = 0, best2 = 0;
//        int i = 0, j = 0;
//        while (i < m || j < n) {
//            if (i < m && j < n) {
//                if (nums1[i] < nums2[j]) {
//                    best1 += nums1[i];
//                    ++i;
//                }
//                else if (nums1[i] > nums2[j]) {
//                    best2 += nums2[j];
//                    ++j;
//                }
//                else {
//                    long long best = max(best1, best2) + nums1[i];
//                    best1 = best2 = best;
//                    ++i;
//                    ++j;
//                }
//            }
//            else if (i < m) {
//                best1 += nums1[i];
//                ++i;
//            }
//            else if (j < n) {
//                best2 += nums2[j];
//                ++j;
//            }
//        }
//        return max(best1, best2) % mod;
//    }
//};

//2919. 使数组变美的最小增量运算数

//给你一个下标从 0 开始、长度为 n 的整数数组 nums ，和一个整数 k 。
//你可以执行下述 递增 运算 任意 次（可以是 0 次）：
//从范围[0, n - 1] 中选择一个下标 i ，并将 nums[i] 的值加 1 。
//如果数组中任何长度 大于或等于 3 的子数组，其 最大 元素都大于或等于 k ，则认为数组是一个 美丽数组 。
//以整数形式返回使数组变为 美丽数组 需要执行的 最小 递增运算数。
//子数组是数组中的一个连续 非空 元素序列。

//class Solution {
//public:
//    long long minIncrementOperations(vector<int>& nums, int k) {
//        long long f0 = 0, f1 = 0, f2 = 0;
//        for (int x : nums) {
//            long long inc = f0 + max(k - x, 0);
//            f0 = min(inc, f1);
//            f1 = min(inc, f2);
//            f2 = inc;
//        }
//        return f0;
//    }
//};

//801. 使序列递增的最小交换次数

//我们有两个长度相等且不为空的整型数组 nums1 和 nums2 。在一次操作中，我们可以交换 nums1[i] 和 nums2[i]的元素。
//例如，如果 nums1 = [1, 2, 3, 8] ， nums2 = [5, 6, 7, 4] ，你可以交换 i = 3 处的元素，得到 nums1 = [1, 2, 3, 4] 和 nums2 = [5, 6, 7, 8] 。
//返回 使 nums1 和 nums2 严格递增 所需操作的最小次数 。
//数组 arr 严格递增 且  arr[0] < arr[1] < arr[2] < ... < arr[arr.length - 1] 。
//注意：
//用例保证可以实现操作。

//class Solution {
//public:
//    int minSwap(vector<int>& nums1, vector<int>& nums2) {
//        int n = nums1.size(), not_swap = 0, swap = 1;
//        for (int i = 1; i < n; ++i) {
//            int ns = n, s = n; // 答案不会超过 n，故初始化成 n 方便后面取 min
//            if (nums1[i - 1] < nums1[i] && nums2[i - 1] < nums2[i]) {
//                ns = not_swap;
//                s = swap + 1;
//            }
//            if (nums2[i - 1] < nums1[i] && nums1[i - 1] < nums2[i]) {
//                ns = min(ns, swap);
//                s = min(s, not_swap + 1);
//            }
//            not_swap = ns;
//            swap = s;
//        }
//        return min(not_swap, swap);
//    }
//};

//3434. 子数组操作后的最大频率

//给你一个长度为 n 的数组 nums ，同时给你一个整数 k 。
//你可以对 nums 执行以下操作 一次 ：
//选择一个子数组 nums[i..j] ，其中 0 <= i <= j <= n - 1 。
//选择一个整数 x 并将 nums[i..j] 中 所有 元素都增加 x 。
//请你返回执行以上操作以后数组中 k 出现的 最大 频率。
//子数组 是一个数组中一段连续 非空 的元素序列。

//class Solution {
//public:
//    int maxFrequency(vector<int>& nums, int k) {
//        int f0 = 0, f1[51]{}, max_f1 = 0, f2 = 0;
//        for (int x : nums) {
//            f2 = max(f2, max_f1) + (x == k);
//            f1[x] = max(f1[x], f0) + 1;
//            f0 += (x == k);
//            max_f1 = max(max_f1, f1[x]);
//        }
//        return max(max_f1, f2);
//    }
//};

//1955. 统计特殊子序列的数目

//特殊序列 是由 正整数 个 0 ，紧接着 正整数 个 1 ，最后 正整数 个 2 组成的序列。
//比方说，[0, 1, 2] 和[0, 0, 1, 1, 1, 2] 是特殊序列。
//相反，[2, 1, 0] ，[1] 和[0, 1, 2, 0] 就不是特殊序列。
//给你一个数组 nums （仅 包含整数 0，1 和 2），请你返回 不同特殊子序列的数目 。由于答案可能很大，请你将它对 109 + 7 取余 后返回。
//一个数组的 子序列 是从原数组中删除零个或者若干个元素后，剩下元素不改变顺序得到的序列。如果两个子序列的 下标集合 不同，那么这两个子序列是 不同的 。

//class Solution {
//    const int MOD = 1e9 + 7;
//public:
//    int countSpecialSubsequences(vector<int>& nums) {
//        int n = nums.size();
//        long long f0 = 0LL, f1 = 0LL, f2 = 0LL;
//        for (auto x : nums) {
//            if (x == 0) f0 = (f0 + f0 + 1) % MOD; //连接到原来结尾0的序列上/自己新开一个序列
//            if (x == 1) f1 = (f1 + f1 + f0) % MOD; //连接到原来结尾0/1的序列上
//            if (x == 2) f2 = (f2 + f2 + f1) % MOD; //连接到原来结尾1/2的序列上
//        }
//        return f2;
//    }
//};

//3068. 最大节点价值之和

//给你一棵 n 个节点的 无向 树，节点从 0 到 n - 1 编号。树以长度为 n - 1 下标从 0 开始的二维整数数组 edges 的形式给你，其中 edges[i] = [ui, vi] 表示树中节点 ui 和 vi 之间有一条边。
//同时给你一个 正 整数 k 和一个长度为 n 下标从 0 开始的 非负 整数数组 nums ，其中 nums[i] 表示节点 i 的 价值 。
//Alice 想 最大化 树中所有节点价值之和。为了实现这一目标，Alice 可以执行以下操作 任意 次（包括 0 次）：
//选择连接节点 u 和 v 的边[u, v] ，并将它们的值更新为：
//nums[u] = nums[u] XOR k
//nums[v] = nums[v] XOR k
//请你返回 Alice 通过执行以上操作 任意次 后，可以得到所有节点 价值之和 的 最大值 。

//class Solution {
//public:
//    long long maximumValueSum(vector<int>& nums, int k, vector<vector<int>>& edges) {
//        long long f0 = 0, f1 = LLONG_MIN;
//        for (int x : nums) {
//            long long tmp = max(f1 + x, f0 + (x ^ k));
//            f0 = max(f0 + x, f1 + (x ^ k));
//            f1 = tmp;
//        }
//        return f0;
//    }
//};

//3640. 三段式数组 II

//给你一个长度为 n 的整数数组 nums。
//三段式子数组 是一个连续子数组 nums[l...r]（满足 0 <= l < r < n），并且存在下标 l < p < q < r，使得：
//nums[l...p] 严格 递增，
//nums[p...q] 严格 递减，
//nums[q...r] 严格 递增。
//请你从数组 nums 的所有三段式子数组中找出和最大的那个，并返回其 最大 和。

//class Solution {
//public:
//    long long maxSumTrionic(vector<int>& nums) {
//        const long long NEG_INF = LLONG_MIN / 2; // 除 2 防止下面加法（和负数相加）溢出
//        long long ans = NEG_INF, f1 = NEG_INF, f2 = NEG_INF, f3 = NEG_INF;
//        for (int i = 1; i < nums.size(); i++) {
//            long long x = nums[i - 1], y = nums[i];
//            f3 = x < y ? max(f3, f2) + y : NEG_INF;
//            f2 = x > y ? max(f2, f1) + y : NEG_INF;
//            f1 = x < y ? max(f1, x) + y : NEG_INF;
//            ans = max(ans, f3);
//        }
//        return ans;
//    }
//};

//2272. 最大波动的子字符串

//字符串的 波动 定义为子字符串中出现次数 最多 的字符次数与出现次数 最少 的字符次数之差。
//给你一个字符串 s ，它只包含小写英文字母。请你返回 s 里所有 子字符串的 最大波动 值。
//子字符串 是一个字符串的一段连续字符序列。

//class Solution {
//public:
//    int largestVariance(string s) {
//        int ans = 0;
//        for (char a = 'a'; a <= 'z'; a++) {
//            for (char b = 'a'; b <= 'z'; b++) {
//                if (b == a) {
//                    continue;
//                }
//                int f0 = 0, f1 = INT_MIN;
//                for (char ch : s) {
//                    if (ch == a) {
//                        f0 = max(f0, 0) + 1;
//                        f1++;
//                    }
//                    else if (ch == b) {
//                        f1 = f0 = max(f0, 0) - 1;
//                    } // else f0 = max(f0, 0); 可以留到 ch 等于 a 或者 b 的时候计算，f1 不变
//                    ans = max(ans, f1);
//                }
//            }
//        }
//        return ans;
//    }
//};

//3661. 可以被机器人摧毁的最大墙壁数目

//一条无限长的直线上分布着一些机器人和墙壁。给你整数数组 robots ，distance 和 walls：
//robots[i] 是第 i 个机器人的位置。
//distance[i] 是第 i 个机器人的子弹可以行进的 最大 距离。
//walls[j] 是第 j 堵墙的位置。
//每个机器人有 一颗 子弹，可以向左或向右发射，最远距离为 distance[i] 米。
//子弹会摧毁其射程内路径上的每一堵墙。机器人是固定的障碍物：如果子弹在到达墙壁前击中另一个机器人，它会 立即 在该机器人处停止，无法继续前进。
//返回机器人可以摧毁墙壁的 最大 数量。
//注意：
//墙壁和机器人可能在同一位置；该位置的墙壁可以被该位置的机器人摧毁。
//机器人不会被子弹摧毁。

//class Solution {
//public:
//    int maxWalls(vector<int>& robots, vector<int>& distance, vector<int>& walls) {
//        int n = robots.size();
//        struct Pair { int x, d; };
//        vector<Pair> a(n);
//        for (int i = 0; i < n; i++) {
//            a[i] = { robots[i], distance[i] };
//        }
//        ranges::sort(a, {}, &Pair::x);
//        ranges::sort(walls);
//
//        vector memo(n, array<int, 2>{-1, -1}); // -1 表示没有计算过
//        auto dfs = [&](this auto&& dfs, int i, int j) -> int {
//            if (i < 0) {
//                return 0;
//            }
//            int& res = memo[i][j]; // 注意这里是引用
//            if (res != -1) { // 之前计算过
//                return res;
//            }
//
//            auto [x, d] = a[i];
//            // 往左射，墙的坐标范围为 [left_x, x]
//            int left_x = x - d;
//            if (i > 0) {
//                left_x = max(left_x, a[i - 1].x + 1); // +1 表示不能射到左边那个机器人
//            }
//            int left = ranges::lower_bound(walls, left_x) - walls.begin();
//            int cur = ranges::upper_bound(walls, x) - walls.begin();
//            res = dfs(i - 1, 0) + cur - left; // 下标在 [left, cur-1] 中的墙都能摧毁
//
//            // 往右射，墙的坐标范围为 [x, right_x]
//            int right_x = x + d;
//            if (i + 1 < n) {
//                auto [x2, d2] = a[i + 1];
//                if (j == 0) { // 右边那个机器人往左射
//                    x2 -= d2;
//                }
//                right_x = min(right_x, x2 - 1); // -1 表示不能射到右边那个机器人（或者它往左射到的墙）
//            }
//            int right = ranges::upper_bound(walls, right_x) - walls.begin();
//            cur = ranges::lower_bound(walls, x) - walls.begin();
//            res = max(res, dfs(i - 1, 1) + right - cur); // 下标在 [cur, right-1] 中的墙都能摧毁
//            return res;
//            };
//
//        return dfs(n - 1, 1);
//    }
//};

//LCP 19. 秋叶收藏集

//小扣出去秋游，途中收集了一些红叶和黄叶，他利用这些叶子初步整理了一份秋叶收藏集 leaves， 字符串 leaves 仅包含小写字符 r 和 y， 其中字符 r 表示一片红叶，字符 y 表示一片黄叶。
//出于美观整齐的考虑，小扣想要将收藏集中树叶的排列调整成「红、黄、红」三部分。每部分树叶数量可以不相等，但均需大于等于 1。
//每次调整操作，小扣可以将一片红叶替换成黄叶或者将一片黄叶替换成红叶。请问小扣最少需要多少次调整操作才能将秋叶收藏集调整完毕。

//class Solution {
//public:
//    int minimumOperations(string leaves) {
//        int n = leaves.size();
//        vector<vector<int>> f(n, vector<int>(3));
//        f[0][0] = (leaves[0] == 'y');
//        f[0][1] = f[0][2] = f[1][2] = INT_MAX;
//        for (int i = 1; i < n; ++i) {
//            int isRed = (leaves[i] == 'r');
//            int isYellow = (leaves[i] == 'y');
//            f[i][0] = f[i - 1][0] + isYellow;
//            f[i][1] = min(f[i - 1][0], f[i - 1][1]) + isRed;
//            if (i >= 2) {
//                f[i][2] = min(f[i - 1][1], f[i - 1][2]) + isYellow;
//            }
//        }
//        return f[n - 1][2];
//    }
//};